﻿package zf.data.ds
{
	import zf.data.ds.node.SListNode;

	/**
	 * 单向数据链表，包括头和尾指针 
	 * @author Mike.zhang
	 * @langversion 3.0 
	 * @playerversion Flash 9 
	 * 
	 * @see zf.data.ds.node.SListNode
	 */
	public class SLinkedList implements ILinkedList
	{
		private var _head:SListNode;
		private var _tail:SListNode;

		/**
		 * @private 
		 */
		protected var _length:uint;
		/**
		 * 单向数据链表 
		 * @param args 链表数据
		 * 
		 */
		public function SLinkedList (... args)
		{
			_head=_tail=null;
			_length=0;
			if (args.length > 0)
			{
				append.apply (this,args);
			}
		}

		/**
		 * 头指针，指向第一个节点 
		 * @return 节点
		 * 
		 */
		public function get head ():SListNode
		{
			return _head;
		}

		public function set head (v:SListNode):void
		{
			_head=v;
		}

		/**
		 * 尾指针，指向最后一个节点 
		 * @return 节点
		 * 
		 */
		public function get tail ():SListNode
		{
			return _tail;
		}

		public function set tail (v:SListNode):void
		{
			_tail=v;
		}

		/**
		 * 链表长度，总计的节点个数 
		 * @return 链表长度
		 * 
		 */
		public function get length ():uint
		{
			return _length;
		}

		/**
		 * 添加一个或多个数据到链表尾，返回添加的第一个链表节点 
		 * @param args 要添加的一个或多个数据
		 * @return 添加到链表的第一个数据构成的节点
		 * 
		 */
		public function append (... args):SListNode
		{
			var l:uint=args.length;
			//var sll:SLinkedList=new SLinkedList(args[0]);
			var node:SListNode=new SListNode(args[0]);
			if (head)
			{
				tail.next=node;
				tail=node;
			}
			else
			{
				head=tail=node;
			}
			if (l > 1)
			{
				var t:SListNode=node;
				for (var i:uint=1; i < l; i++)
				{
					node=new SListNode(args[i]);
					tail.next=node;
					tail=node;
				}
				_length+= l;
				return t;
			}
			_length++;
			return node;
		}
		/**
		 * @inheritDoc
		 * 
		 */
		public function clear ():void
		{
			var node:SListNode=head;
			head=null;

			var next:SListNode;
			while (node)
			{
				next=node.next;
				node.next=null;
				node=next;
			}
			tail=null;
			_length=0;
		}
		/**
		 * 连接一个或多个SLinkedList链表，并返回连接成的新链表，本链表保持不变 
		 * @param args 要连接的一个或多个SLinkedList链表
		 * @return 返回一个新的SLinkedList链表
		 * 
		 */
		public function concat (... args):SLinkedList
		{
			var c:SLinkedList=new SLinkedList  ;
			var a:SLinkedList;
			var n:SListNode;

			n=head;
			while (n)
			{
				c.append (n.data);
				n=n.next;
			}
			var k:uint=args.length;
			for (var i:uint=0; i < k; i++)
			{
				a=args[i];
				n=a.head;
				while (n)
				{
					c.append (n.data);
					n=n.next;
				}
			}
			return c;
		}
		/**
		 * @inheritDoc
		 */
		public function contains (obj:*):Boolean
		{
			var node:SListNode=head;
			while (node)
			{
				if (node.data == obj)
				{
					return true;
				}
				node=node.next;
			}
			return false;
		}
		/**
		 * 克隆链表 
		 * @return 链表 
		 * 
		 */
		public function clone ():SLinkedList
		{
			if (head)
			{
				var node:SListNode=head;
				var sll:SLinkedList=new SLinkedList  ;
				while (node)
				{
					sll.append (node.data);
					node=node.next;
				}
				return sll;
			}
			return null;
		}
		/**
		 * 创建一个指针，该指针初始指向链表头节点 
		 * @return 指针 SListPointer
		 * 
		 */
		public function creatPointer ():SListPointer
		{
			return new SListPointer(this,head);
		}
		/**
		 * 在链表中slp所指向的节点后面插入一个数据为obj的节点 
		 * @param slp 指针，指向链表的节点
		 * @param obj 数据，要生成节点的数据
		 * @return 插入后形成的节点
		 * 
		 */
		public function insertAfter (slp:SListPointer,obj:*):SListNode
		{
			if (slp.list != this)
			{
				return null;
			}
			if (slp.node)
			{
				var node:SListNode=new SListNode(obj);
				slp.node.insertAfter (node);
				if (slp.node == tail)
				{
					tail=node;
				}
				_length++;
				return node;
			}
			else
			{
				return append(obj);
			}
		}
		/**
		 * @inheritDoc
		 */
		public function isEmpty ():Boolean
		{
			return (((((((((((((((((((((((((((((((((((((((((((((((((((_length == 0)))))))))))))))))))))))))))))))))))))))))))))))))));
		}
		/**
		 * 使用全等（===），从form指针指向的节点开始，查找数据为obj的节点，并返回指向obj数据节点的指针。
		 * @param obj 待查找的数据
		 * @param form 查找开始的指针
		 * @return 如果有，返回指向该数据所在节点的指针，否则返回null
		 * 
		 */
		public function nodeOf (obj:*,form:SListPointer=null):SListPointer
		{
			if (form != null)
			{
				if (form.list != this)
				{
					return null;
				}
			}
			var node:SListNode=form == null?head:form.node;
			while (node)
			{
				if (node.data === obj)
				{
					return new SListPointer(this,node);
				}
				node=node.next;
			}
			return null;
		}

		/**
		 * 删除指针指向的节点 
		 * @param p 指针，指向要删除的节点
		 * @return 删除成功返回true
		 * 
		 */
		public function remove (p:SListPointer):Boolean
		{
			if (p.list != this || ! p.node)
			{
				return false;
			}
			if (p.node == head)
			{
				p.next ();
				removeHead ();
				return true;
			}
			var node:SListNode=getPrev(p);
			if (! node)
			{
				return false;
			}
			if (node.next == tail)
			{
				tail=node;
			}
			node.next=p.node.next;
			_length--;
			//p.next();
			return true;
		}
		/**
		 * 删除链表中最后一个节点，并返回该节点数据 
		 * @return 数据
		 * 
		 */
		public function removeTail ():*
		{
			if (head)
			{
				var node:SListNode=head;
				while (node.next != tail)
				{
					node=node.next;
				}
				tail=node;
				node=node.next;
				tail.next=null;
				_length--;
				return node.data;
			}
			return null;
		}
		/**
		 * 删除链表中第一个节点，并返回该节点数据 
		 * @return 数据
		 * 
		 */
		public function removeHead ():*
		{
			if (head)
			{
				var node:SListNode=head;
				if (head.next)
				{
					head=head.next;
				}
				node.next=null;
				_length--;
				return node.data;
			}
			return null;
		}
		/**
		 * 倒转链表操作 
		 * 
		 */
		public function reverse ():void
		{
			if (_length < 2)
			{
				return;
			}
			var arr:Array=new Array  ;
			var node:SListNode=head;
			while (node)
			{
				arr.push (node);
				node=node.next;
			}
			node=head=arr[_length - 1];
			for (var i:uint=_length - 1; i > 0; i--)
			{
				node.next=arr[i - 1];
				node=node.next;
				//arr[i].next=arr[i-1];
			}
			//arr[0].next=null;
			//head=arr[_length-1];
			//tail=arr[0];
			node.next=null;
			tail=node;
			arr=null;
		}
		/**
		 * 将链表数据转化为数组 
		 * @return 数组
		 * 
		 */
		public function toArray ():Array
		{
			if (head)
			{
				var node:SListNode=head;
				var arr:Array=new Array  ;
				while (node)
				{
					arr.push (node.data);
					node=node.next;
				}
				return arr;
			}
			return null;
		}
		/**
		 * @private
		 * 获取指针指向节点的前一个节点，如果不存在该节点返回null 
		 * @param form 指针
		 * @return 指针指向的前一个节点，如果不存在返回null
		 * 
		 */
		protected function getPrev (form:SListPointer):SListNode
		{
			if (! form || ! form.node || form.node == head || head == null)
			{
				return null;
			}
			var node:SListNode=head;
			while (node.next != form.node)
			{
				node=node.next;
				if (! node)
				{
					return null;
				}
			}
			return node;
		}
		/**
		 * 添加或删除链表中的数据，返回一个被删除的节点组成的链表。同时start指针将指向返回的链表的头
		 * @param start 起始指针
		 * @param deleteCount 要操作的节点个数
		 * @param args 数据
		 * @return 被删除节点组成的链表
		 * 
		 */
		/*public function splice(start:SListPointer, deleteCount:uint = uint.MAX_VALUE, ...args):SLinkedList
		{
		if (start) 
		{
		if (start.list != this) 
		{
		return null;
		}
		}
		
		if (start.node)
		{
		var s:SListNode = start.node;
		var t:SListNode = head;
		while (t.next != s)
		{
		t = t.next;
		}
		
		var c:SLinkedList = new SLinkedList();
		var i:int, k:int;
		
		if (deleteCount == uint.MAX_VALUE)
		{
		if (start.node == tail) 
		{
		return c;
		} 
		while (start.node)
		{
		c.append(start.node.data);
		start.remove();
		}
		start.list = c;
		start.node = s;
		return c;
		}
		else
		{
		for (i = 0; i < deleteCount; i++)
		{
		if (start.node)
		{
		c.append(start.node.data);
		start.remove();
		}
		else
		{
		break;
		}
		}
		}
		
		k = args.length;
		if (k > 0)
		{
		if (_length == 0)
		{
		for (i = 0; i < k; i++)
		{
		append(args[i]);
		}
		}
		else
		{
		var n:SListNode;
		if (t == null)
		{
		n = prepend(args[0]);
		for (i = 1; i < k; i++)
		{
		n.insertAfter(new SListNode(args[i]));
		if (n == tail)
		{
		tail = n.next;
		} 
		n = n.next;
		_length++;
		}
		}
		else
		{
		n = t;
		for (i = 0; i < k; i++)
		{
		n.insertAfter(new SListNode(args[i]));
		if (n == tail)
		{
		tail = n.next;
		} 
		n = n.next;
		_length++;
		}
		}
		}
		start.node = n;
		}
		else
		start.node = s;
		
		start.list = c;
		return c;
		}
		return null;
		}*/
		public function splice (start:SListPointer=null,deleteCount:uint=uint.MAX_VALUE,... args):SLinkedList
		{
			if (start)
			{
				if (start.list != this)
				{
					return null;
				}
			}
			else
			{
				start=this.creatPointer();
			}

			var s:SListNode=getPrev(start);

			var node:SListNode=start.node;
			var pn:SListNode;
			var sll:SLinkedList=new SLinkedList  ;
			for (var i:uint=0; i < deleteCount && node; i++)
			{
				sll.append (node.data);
				//start.remove();
				pn=node;
				node=node.next;
				pn.next=null;

			}
			var e:SListNode=node;
			_length-= i;
			var l:uint=args.length;
			var ts:SListNode;
			var te:SListNode;
			if (l > 0)
			{
				ts=new SListNode(args[0]);
				node=ts;
				for (i=1; i < l; i++)
				{
					node.next=new SListNode(args[i]);
					node=node.next;
				}
				te=node;
				if (_length == 0)
				{
					head=ts;
					tail=te;
					_length=l;
				}
				else
				{
					if (! s)
					{
						head=ts;
						te.next=e;
					}
					else if (! e)
					{
						tail=te;
						s.next=ts;
					}
					else
					{
						s.next=ts;
						te.next=e;
					}
					_length+= l;
				}
				start.list=sll;
				start.node=sll.head;
				return sll;
			}
			else
			{
				if (! s)
				{
					head=e;
				}
				else if (! e)
				{
					tail=s;
				}
				else
				{
					s.next=e;
				}
				start.list=sll;
				start.node=sll.head;
				return sll;
			}
			return null;
		}
		/**
		 * 返回链表的描述信息 
		 * @return 格式[数据1,数据2, ...]
		 * 
		 */
		public function toString ():String
		{
			if (isEmpty())
			{
				return null;
			}
			var node:SListNode=head;
			//var str:String="[(Length:"+_length+" head:"+head+" tail:"+tail+") ";
			var str:String="[";
			while (node)
			{
				str+= node.toString() + ",";
				node=node.next;
			}
			str=str.slice(0,str.length - 1);
			str+= "]";
			return str;
		}
	}
}